package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.ArrayList;
import java.util.List;

/**
 * todo
 *
 * @author wanwei
 * @since 2022-03-16 09:52
 */
public class AS77组合 {

    public static void main(String[] args) {
        int n = 4, k = 2;
        System.out.println(combine(n, k));
    }

    public static List<List<Integer>> combine(int n, int k) {
        if (k > n) {
            return new ArrayList<>();
        }
        List<List<Integer>> listAll = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            List<Integer> list = new ArrayList<>();
            list.add(i);
            combine2(n, k - 1, list, listAll);
        }
        return listAll;
    }

    public static void combine2(int n, int k, List<Integer> origin, List<List<Integer>> listAll) {
        if (k == 0) {
            listAll.add(origin);
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (i <= origin.get(origin.size() - 1)) {
                continue;
            }
            List<Integer> listNew = new ArrayList<>();
            listNew.addAll(origin);
            listNew.add(i);
            combine2(n, k - 1, listNew, listAll);
        }
    }
}
